Routing devices within a network, often referred to as routers, maintain tables of routing information that describe available routes through the network. Network routers maintain routing information that describes available routes through the network. Upon receiving a packet, a router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more routing protocols, such as an interior gateway protocol (IGP) or Border Gateway Protocol (BGP).
The term “link” is often used to refer to the connection between two devices on a network. The link may be a physical connection such as a copper wire, a coaxial cable, any of a host of different fiber optic lines or a wireless connection. In addition, network devices may define “virtual” or “logical” links, and map the virtual links to the physical links. In other words, the use of virtual links provides a degree of abstraction. As networks grow in size and complexity, the traffic on any given link may approach a maximum bandwidth capacity for the link, thereby leading to congestion and loss.
Multi-protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. Using MPLS, a source device can request a path through a network, i.e., a Label Switched Path (LSP). An LSP defines a distinct path through the network to carry packets from the source device to a destination device. A short label associated with a particular LSP is affixed to packets that travel through the network via the LSP. Routers along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path. LSPs may be used for a variety of traffic engineering purposes including bandwidth management and quality of service (QoS).
Traffic engineering may be applied within a network for a variety of purposes, such as to route traffic around network failures or congested links or to direct certain traffic along a particular path through the network that meets a set of explicit requirements. Historically, MPLS label distribution was driven by protocols such as label distribution protocol (LDP), Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE) and labeled Border Gateway Protocol (LBGP). Procedures for LDP by which label switching routers (LSRs) distribute labels to support MPLS forwarding along normally routed paths are described in L. Anderson, “LDP Specification,” RFC 3036, Internet Engineering Task Force (IETF), January 2001, the entire contents of which are incorporated by reference herein. RSVP-TE uses constraint information, such as bandwidth availability or shared-risk link group (SRLG) information, to compute and establish LSPs within a resource-constrained network. RSVP-TE may use bandwidth availability information accumulated by a link-state interior routing protocol, such as the Intermediate System-Intermediate System (IS-IS) protocol or the Open Shortest Path First (OSPF) protocol, extended to carry traffic engineering information.
Head-end routers of an LSP are commonly known as ingress routers, while routers at the tail-end of the LSP are commonly known as egress routers. Ingress and egress routers, as well as intermediate routers along the LSP that support MPLS, are referred to generically as label switching routers (LSRs). A set of packets to be forwarded along the LSP is referred to as a forwarding equivalence class (FEC). A plurality of FECs may exist for each LSP, but there may be only one active LSP for any given FEC. A FEC definition typically includes the IP address of the destination of the LSP, e.g., an IP address assigned to the egress router of the LSP. The ingress label edge router (LER) uses routing information, propagated from the egress LER, to determine the LSP, to assign labels for the LSP, and to affix a label to each packet of the FEC. Ingress and egress LERs may be referred to herein as “edge routers,” “edge nodes,” or “end nodes.” The LSRs use MPLS protocols to receive MPLS label mappings from downstream LSRs and to advertise MPLS label mappings to upstream LSRs. When an LSR receives an MPLS packet from an upstream router, it switches the MPLS label according to the information in its forwarding table and forwards the packet to the appropriate downstream LSR or LER. The egress LER removes the label from the packet and forwards the packet to its destination in accordance with non-label based packet forwarding techniques.
In general, each router along the LSP maintains a context that associates a FEC with an incoming label and an outgoing label. In this manner, when an LSR receives a labeled packet, the LSR may swap the label (i.e., the incoming label) with the outgoing label by performing a lookup in the context. The LSR may then forward the packet to the next LSR or LER along the LSP. The next router along the LSP is commonly referred to as a downstream router or a next hop.
In other words, once a packet is mapped on to an LSP by an LER, the LSRs along the LSP forward the packet based on labels attached to the packet rather than making independent forwarding decisions based on the packet destination and the LSRs' routing information. A Traffic Engineering MPLS LSP (TE LSP) may in this way be used to define and implement a path from a source device to a destination device that satisfies requirements for certain traffic transported by the network.
The explicit requirements that must be satisfied by an LSP represent constraints upon the set of possible paths from the source device to the destination device. These constraints, such as available bandwidth and link attributes/coloring, direct the path computation device executing shortest path first algorithms to compute a satisfactory path for the single LSP with regard to the constraints. A shortest path algorithm may include Dijkstra, Bellman-Ford, Flood-fill, or another SPF algorithm. The network routers then establish an LSP that matches the computed path and, using the LSP, forward traffic in a manner that satisfies the constraints. The path computation device may then compute a satisfactory path for another LSP, and then another, and so on until the path computation device is unable to pack any additional LSP into the network.
Constrained shortest-path first (CSPF) thus represents a fundamental building block for traffic engineering systems, including MPLS and Generalized MPLS (GMPLS) networks. Moreover, as constraint-based path computation proceeds for multiple LSPs, when each LSP is successively loaded on the network, the available bandwidth is reduced. As a result, constraint-based path computation in large networks may be a complex, time- and resource-consuming operation.